/*
 * cfg.cpp
 *
 *  Created on: Jun 20, 2010
 *      Author: vincent
 */

#include "flow.h"
#include "debug.h"
#include <cassert>
#include <vector>
#include <map>
#include <bitset>
#include <cstdlib>
#include <sstream>
#include <algorithm>
#include <stdexcept>

using namespace std;

CFG::CFG(FunctionSymbol *sym){
    startBlock = 0;
    endBlock = 0;
    domTree = 0;
    funcSym = sym;
}

/// @brief  Generate the basic blocks from opcodes
/// a basic block is code that has one entry point
/// (i.e., no code within it is the destination of a jump instruction),
/// one exit point and no jump instructions contained within it
/// (i.e., a sequence of instructions which are all executed if the first one in the sequence is executed).
/// The start of a basic block may be jumped to from more than one location.
/// The end of a basic block may be a jump instruction or the statement before the destination of a jump instruction
void CFG::makeBlocks(){
    //TODO: adjust bitset size
    bitset<1024*32> leader;
    OpCodeGen::ops_type &ops = funcSym->ops;
    assert(ops.size() <= 1024*32 && "too many opcodes");

    if(ops.empty()){
        // no statement
        return;
    }

    // the firstOp with -1 indicates it isn't normal block
    startBlock = new BasicBlock(-1);
    endBlock = new BasicBlock(-1);

    // 1. Mark the leaders
    // The first instruction is a leader.
    // The target of a conditional or an unconditional goto/jump instruction is a leader.
    // The instruction that immediately follows a conditional or an unconditional goto/jump instruction is a leader.
    leader.set(1);
    for(int i = 1;i <= ops.size();i++){
        Opcode *op = ops[i];
        if(op->isTerminal()){
            if(CondGotoOp *o = dynamic_cast<CondGotoOp*>(op)){
                leader.set(o->trueLabel);
                leader.set(o->falseLabel);
            }else if(GotoOp *o = dynamic_cast<GotoOp*>(op)){
                leader.set(i+1);
                leader.set(o->dstLabel);
            }else{
                assert(0 && "Not recognized opcodes;");
            }
        }
    }

    // 2. Build the blocks
    // Starting from a leader, the set of all following instructions until and not
    // including the next leader is the basic block corresponding to the starting leader
    map<int,BasicBlock*>    blkmap;
    BasicBlock *blk = 0;
    for(int i = 1;i <= ops.size();i++){
        if(leader[i]){
            blk = new BasicBlock(i);
            blkmap[i] = blk;
            blocks.push_back(blk);
        }
        blk->insertOp(ops[i]);
    }

    // 3. Build the edges
    int isNoCtrl = 0;
    BasicBlock *pbb = 0;
    for(iterator it = blocks.begin();it != blocks.end();it++){
        BasicBlock *bb = *it;
        const Opcode  *op = bb->getLastOp();

        if(isNoCtrl && pbb){
            // the previous bb falls through into this one
            pbb->insertSucc(bb);
            bb->insertPred(pbb);
        }

        if(op->isTerminal()){
            if(const CondGotoOp *o = dynamic_cast<const CondGotoOp*>(op)){
                BasicBlock *b1 = blkmap[o->trueLabel];
                BasicBlock *b2 = blkmap[o->falseLabel];

                assert(b1 && b2 && "CondGotoOp jumps to undefined BasicBlock");
                bb->insertSucc(b1);
                bb->insertSucc(b2);
                b1->insertPred(bb);
                b2->insertPred(bb);
            }else if(const GotoOp *o = dynamic_cast<const GotoOp*>(op)){
                BasicBlock  *b1 = blkmap[o->dstLabel];

                assert(b1 && "GotoOp jumps to undefined BasicBlock");
                bb->insertSucc(b1);
                b1->insertPred(bb);
            }
            isNoCtrl = 0;
        }else{
            isNoCtrl = 1;
        }

        pbb = bb;
    }

    startBlock->insertSucc(*blocks.begin());
    (*blocks.begin())->insertPred(startBlock);
    endBlock->insertPred(blocks.back());
    blocks.back()->insertSucc(endBlock);
}

void CFG::setDfsNumber(){
    // blocks dfs-numbering of reverse postorder without recursive
    // also set the number for *start* and *end*
    int n = blocks.size() + 1;
    vector<BasicBlock*> workList;

    if(!blocks.size()){
        // no blocks
        return;
    }

    workList.push_back(startBlock);

    while(!workList.empty()){
        BasicBlock *bb = workList.back();

        // non-visited block with dfsNo -1
        if(bb->getDfsNo() == -1){
            // temporarily set the No. to 0 to avoid being visited again
            bb->setDfsNo(0);
            for(BasicBlock::succ_iterator succ_it = bb->getSuccBegin();
                succ_it != bb->getSuccEnd();succ_it++){

                if((*succ_it)->getDfsNo() == -1){
                    // haven't be visited yet(not in workList)
                    workList.push_back(*succ_it);
                }
            }
        }else if(bb->getDfsNo() == 0){
            // all bb's children are visited
            bb->setDfsNo(n--);
            blocksDfsOrder.push_front(bb);
            workList.pop_back();
        }
    }

    cout<<"dfsOrder.size: "<<blocksDfsOrder.size()<<" blocks.size: "<<blocks.size()<<endl;
    //assert(n == 0 && "the dfs number of start block is not 0");
    //start->setDfsNo(n);
}

BasicBlock* CFG::getBlockByDfsno(int i){
    try{
        return blocksDfsOrder[i];
    }catch(out_of_range e){
        cerr<<"out of range in CFG::getBlockByDfsno() with i = "<<i<<endl;
    }

    return 0;
}

void CFG::setup(){
    makeBlocks();

    if(blocks.empty()){
        return;
    }

    setDfsNumber();
    domTree = new DomTree(this);
}

void CFG::printBlocks(GraphPrinter &gp){
    string attrs[] = {"node [shape=box]","edge [color=blue]"};

    if(blocks.empty()){
        return;
    }

    gp.beginSubgraph(funcSym->getName(),attrs,2);
    for(int i = 0;i < blocks.size();i++){
        BasicBlock *bb = blocks[i];
        stringstream ss;
        ss << "Block" << bb->getDfsNo() << "\\n";
        string  label = ss.str();
        for(BasicBlock::iterator it = bb->begin();it != bb->end();it++){
            label += (*it)->getPrintInfo();
            label += "\\n";
        }
        gp.newNode(bb->getDfsNo(),label);
        for(BasicBlock::succ_iterator it = bb->getSuccBegin();it != bb->getSuccEnd();it++){
            gp.newLine(bb->getDfsNo(),(*it)->getDfsNo());
        }
    }
    // start and end block
    string s("START"),e("END");

    // TODO: refactor here
    gp.newNode(startBlock->getDfsNo(),s);
    gp.newNode(endBlock->getDfsNo(),e);
    gp.newLine(startBlock->getDfsNo(),blocks[0]->getDfsNo());

    // print the dom tree
    gp.printLine("edge [style=dotted color=green]");
    /*for(int i = dfsOrder.size() - 1;i > 0;i--){
        // print every blocks' immediate dominator except *start* block
        BasicBlock *bb = dfsOrder[i];
        assert(bb);
        gp.newLine(dfsOrder[bb->getIdom()]->getDfsNo(),bb->getDfsNo());
    }*/
    gp.endSubgraph();
}

